import java.util.ArrayList;

public class Tabu {
    private static int num; // 访问点的数量
    private static int[] now_sol; // 当前解
    private static double now_cost;
    private static int[] best_sol; // 全局最优解
    private static double best_cost;
    private static int[] ob_sol; // 局部最优解（一次邻域搜索的最优解）
    private static double ob_cost;
    private static double[][] matrix; // 访问点的距离矩阵
    private static int[][] tabu; // 禁忌表，里面是禁忌一个邻域动作
    // tabu[i][j] 表示禁忌交换i j位置的访问点
    // tabu[i][j] = 0 时，表示此邻域动作没有被禁忌
    private static int tl; // 禁忌步长
    private static int spe; // 特赦值


    // 使用禁忌搜索解TSP问题
    // 完整的禁忌搜索中需要使用一个禁忌表
    // 禁忌的是一个邻域动作，而不是其他
    public static ArrayList<Integer> solve() {
        // 全局最优解，局部最优解
        // 全局最优解与局部最优解有什么区别吗？
        // 全局最优解是指在整个迭代搜索过程中的最优解，局部最优解是一次迭代的过程中的，当前找到的最优解
        // 他们的特赦准则不同
        // 如果搜索到的解，优于全局最优解，直接特赦
        // 如果搜索到的解，优于局部最优解，但是不满足禁忌长度限制，不能特赦
        // 一次迭代才会出现一个当前解，也就是当前的全局最优解
        // 从当前函数出发，进行研究

        for (int t = 0; t < 100; t++) {
            // 临时解
            int[] temp_sol = new int[num];
            double temp_cost = Double.MAX_VALUE;
            for (int i = 0; i < num; i++) {
                temp_sol[i] = now_sol[i];
            }

            int a = num + 1, b = num + 1;
            int temp = num + 1;
            // 邻域搜索（交换i位置的元素，i+j位置的元素）
            for (int i = 1; i < num; i++) {
                for (int j = 0; j < num; j++) {
                    if (i == j) continue;
                    if (i + j >= num-1) break;

                    // 交换 ij位置的访问点
                    temp = temp_sol[i];
                    temp_sol[i] = temp_sol[j + i];
                    temp_sol[i + j] = temp;
                    temp_cost = calculate(temp_sol);
                    // 藐视准则：（如果比全局最优解优秀，且不是刚刚禁忌的解，那就更新全局最优解）
                    if (temp_cost < best_cost && tabu[i][i + j] < spe) {
                        for (int k = 0; k < num; k++) {
                            best_sol[k] = temp_sol[k];
                            best_cost = temp_cost;
                            a = i;
                            b = i + j;
                        }
                    }
                    // 更新局部最优解（新解优于局部最优解，且未被禁忌）
                    else if (temp_cost < ob_cost && tabu[i][i + j] == 0) {
                        for (int k = 0; k < num; k++) {
                            ob_sol[k] = temp_sol[k];
                            ob_cost = temp_cost;
                            a = i;
                            b = i + j;
                        }
                    }
                }
            }

            // 邻域搜索完成，更新当前解
            if (a != (num + 1)) {
                for (int i = 0; i < num; i++) {
                    now_sol[i] = ob_sol[i];
                }
                now_cost = ob_cost;
                tabu[a][b] = tl;
            }

            // 更新禁忌表
            for (int i = 0; i < num; i++) {
                for (int j = 0; j < num; j++) {
                    if (tabu[i][j] != 0) {
                        tabu[i][j]--;
                    }
                }
            }

        }

        ArrayList<Integer> sol = new ArrayList<>();
        for (int i = 0; i < best_sol.length; i++) {
            sol.add(best_sol[i]);
        }

        return sol;
    }

    // 初始化这个函数
    public static void init(ArrayList<Integer> r, double[][] cost) {
        num = r.size();
        now_sol = new int[num];
        best_sol = new int[num];
        ob_sol = new int[num];
        for (int i = 0; i < r.size(); i++) {
            now_sol[i] = r.get(i);
            best_sol[i] = r.get(i);
            ob_sol[i] = r.get(i);
        }
        tabu = new int[num][num]; // 默认全部为0
        tl = 8;
        spe = 5;
        matrix = new double[cost.length][cost.length];
        for (int i = 0; i < cost.length; i++) {
            for (int j = 0; j < cost.length; j++) {
                matrix[i][j] = cost[i][j];
            }
        }
    }

    // 计算路径成本
    public static double calculate(int[] r) {
        double cost = 0;
        for (int i = 0; i < r.length - 1; i++) {
            cost += matrix[r[i]][r[i + 1]];
        }
        return cost;
    }
}